// 382. 链表随机节点
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 */
// 记录链表所有的元素
var Solution = function (head) {
    this.tempArr = []
    while (head) {
        this.tempArr.push(head.val)
        head = head.next
    }
};

/**
 * @return {number}
 */
Solution.prototype.getRandom = function () {
    const { tempArr } = this
    const len = tempArr.length
    const getRandom = Math.floor(Math.random() * len)
    return tempArr[getRandom]
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(head)
 * var param_1 = obj.getRandom()
 */
// 水塘抽样
var Solution = function (head) {
    this.head = head
};
Solution.prototype.getRandom = function () {
    let i = 1, ans = 0
    for (let node = this.head; node; node = node.next) {
        if (Math.floor(Math.random() * i) === 0) { // 1 / i 的概率选中(替换为答案)
            ans = node.val
        }
        ++i
    }
    return ans
};